package leetcode.editor.offer;

// 剑指 Offer 19. 正则表达式匹配
// https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
class ZhengZeBiaoDaShiPiPeiLcof {
    public static void main(String[] args) {
        Solution solution = new ZhengZeBiaoDaShiPiPeiLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length() + 1, n = p.length() + 1;
            boolean[][] dp = new boolean[m][n];
            dp[0][0] = true;
            for (int i = 2; i < n; i += 2)
                dp[0][i] = dp[0][i - 2] && p.charAt(i - 1) == '*';

            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (p.charAt(j - 1) == '*') {
                        // *匹配0个
                        if (dp[i][j - 2]) dp[i][j] = true;
                        else if (dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) dp[i][j] = true;
                        else if (dp[i - 1][j] && p.charAt(j - 2) == '.') dp[i][j] = true;
                    } else {
                        if (dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) dp[i][j] = true;
                            // p为.
                        else if (dp[i - 1][j - 1] && p.charAt(j - 1) == '.') dp[i][j] = true;
                    }
                }
            }

            return dp[m - 1][n - 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
